home *** CD-ROM | disk | FTP | other *** search
/ Hand Picked Software / Hand Picked Software.iso / aids / ar110 / encode.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  6KB  |  243 lines
  1. /***********************************************************
  2.     encode.c -- sliding dictionary with percolating update
  3. ***********************************************************/
  4. #include "ar.h"
  5. #include <stdlib.h>
  6. #include <string.h>  /* memmove() */
  7.  
  8. #define PERCOLATE  1
  9. #define NIL        0
  10. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  11.  
  12. typedef short node;
  13.  
  14. static uchar *text, *childcount;
  15. static node pos, matchpos, avail,
  16.     *position, *parent, *prev, *next = NULL;
  17. static int remainder, matchlen;
  18.  
  19. #if MAXMATCH <= (UCHAR_MAX + 1)
  20.     static uchar *level;
  21. #else
  22.     static ushort *level;
  23. #endif
  24.  
  25. int numper;
  26.  
  27. static void allocate_memory(void)
  28. {
  29.     if (next != NULL) return;
  30.     text = malloc(DICSIZ * 2 + MAXMATCH);
  31.     level      = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  32.     childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  33.     #if PERCOLATE
  34.       position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  35.     #else
  36.       position = malloc(DICSIZ * sizeof(*position));
  37.     #endif
  38.     parent     = malloc(DICSIZ * 2 * sizeof(*parent));
  39.     prev       = malloc(DICSIZ * 2 * sizeof(*prev));
  40.     next       = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  41.     if (next == NULL) error("Out of memory.");
  42. }
  43.  
  44. static void init_slide(void)
  45. {
  46.     node i;
  47.  
  48.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  49.         level[i] = 1;
  50.         #if PERCOLATE
  51.             position[i] = NIL;  /* sentinel */
  52.         #endif
  53.     }
  54.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  55.     avail = 1;
  56.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  57.     next[DICSIZ - 1] = NIL;
  58.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  59. }
  60.  
  61. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  62.  
  63. static node child(node q, uchar c)
  64.     /* q's child for character c (NIL if not found) */
  65. {
  66.     node r;
  67.  
  68.     r = next[HASH(q, c)];
  69.     parent[NIL] = q;  /* sentinel */
  70.     while (parent[r] != q) r = next[r];
  71.     return r;
  72. }
  73.  
  74. static void makechild(node q, uchar c, node r)
  75.     /* Let r be q's child for character c. */
  76. {
  77.     node h, t;
  78.  
  79.     h = HASH(q, c);
  80.     t = next[h];  next[h] = r;  next[r] = t;
  81.     prev[t] = r;  prev[r] = h;
  82.     parent[r] = q;  childcount[q]++;
  83. }
  84.  
  85. void split(node old)
  86. {
  87.     node new, t;
  88.  
  89.     new = avail;  avail = next[new];  childcount[new] = 0;
  90.     t = prev[old];  prev[new] = t;  next[t] = new;
  91.     t = next[old];  next[new] = t;  prev[t] = new;
  92.     parent[new] = parent[old];
  93.     level[new] = matchlen;
  94.     position[new] = pos;
  95.     makechild(new, text[matchpos + matchlen], old);
  96.     makechild(new, text[pos + matchlen], pos);
  97. }
  98.  
  99. static void insert_node(void)
  100. {
  101.     node q, r, j, t;
  102.     uchar c, *t1, *t2;
  103.  
  104.     if (matchlen >= 4) {
  105.         matchlen--;
  106.         r = (matchpos + 1) | DICSIZ;
  107.         while ((q = parent[r]) == NIL) r = next[r];
  108.         while (level[q] >= matchlen) {
  109.             r = q;  q = parent[q];
  110.         }
  111.         #if PERCOLATE
  112.             t = q;
  113.             while (position[t] < 0) {
  114.                 position[t] = pos;  t = parent[t];
  115.             }
  116.             if (t < DICSIZ) position[t] = pos | PERC_FLAG;
  117.         #else
  118.             t = q;
  119.             while (t < DICSIZ) {
  120.                 position[t] = pos;  t = parent[t];
  121.             }
  122.         #endif
  123.     } else {
  124.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  125.         if ((r = child(q, c)) == NIL) {
  126.             makechild(q, c, pos);  matchlen = 1;
  127.             return;
  128.         }
  129.         matchlen = 2;
  130.     }
  131.     for ( ; ; ) {
  132.         if (r >= DICSIZ) {
  133.             j = MAXMATCH;  matchpos = r;
  134.         } else {
  135.             j = level[r];
  136.             matchpos = position[r] & ~PERC_FLAG;
  137.         }
  138.         if (matchpos >= pos) matchpos -= DICSIZ;
  139.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  140.         while (matchlen < j) {
  141.             if (*t1 != *t2) {  split(r);  return;  }
  142.             matchlen++;  t1++;  t2++;
  143.         }
  144.         if (matchlen >= MAXMATCH) break;
  145.         position[r] = pos;
  146.         q = r;
  147.         if ((r = child(q, *t1)) == NIL) {
  148.             makechild(q, *t1, pos);  return;
  149.         }
  150.         matchlen++;
  151.     }
  152.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  153.     t = next[r];  next[pos] = t;  prev[t] = pos;
  154.     parent[pos] = q;  parent[r] = NIL;
  155.     next[r] = pos;  /* special use of next[] */
  156. }
  157.  
  158. static void delete_node(void)
  159. {
  160.     #if PERCOLATE
  161.         node q, r, s, t, u;
  162.     #else
  163.         node r, s, t, u;
  164.     #endif
  165.  
  166.     if (parent[pos] == NIL) return;
  167.     r = prev[pos];  s = next[pos];
  168.     next[r] = s;  prev[s] = r;
  169.     r = parent[pos];  parent[pos] = NIL;
  170.     if (r >= DICSIZ || --childcount[r] > 1) return;
  171.     #if PERCOLATE
  172.         t = position[r] & ~PERC_FLAG;
  173.     #else
  174.         t = position[r];
  175.     #endif
  176.     if (t >= pos) t -= DICSIZ;
  177.     #if PERCOLATE
  178.         s = t;  q = parent[r];
  179.         while ((u = position[q]) & PERC_FLAG) {
  180.             u &= ~PERC_FLAG;  if (u >= pos) u -= DICSIZ;
  181.             if (u > s) s = u;
  182.             position[q] = (s | DICSIZ);  q = parent[q];
  183.         }
  184.         if (q < DICSIZ) {
  185.             if (u >= pos) u -= DICSIZ;
  186.             if (u > s) s = u;
  187.             position[q] = s | DICSIZ | PERC_FLAG;
  188.         }
  189.     #endif
  190.     s = child(r, text[t + level[r]]);
  191.     t = prev[s];  u = next[s];
  192.     next[t] = u;  prev[u] = t;
  193.     t = prev[r];  next[t] = s;  prev[s] = t;
  194.     t = next[r];  prev[t] = s;  next[s] = t;
  195.     parent[s] = parent[r];  parent[r] = NIL;
  196.     next[r] = avail;  avail = r;
  197. }
  198.  
  199. static void get_next_match(void)
  200. {
  201.     int n;
  202.  
  203.     remainder--;
  204.     if (++pos == DICSIZ * 2) {
  205.         memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
  206.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
  207.         remainder += n;  pos = DICSIZ;  putc('.', stderr);  numper++;
  208.     }
  209.     delete_node();  insert_node();
  210. }
  211.  
  212. void encode(void)
  213. {
  214.     int lastmatchlen;
  215.     node lastmatchpos;
  216.  
  217.     numper=0;
  218.  
  219.     allocate_memory();  init_slide();  huf_encode_start();
  220.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);
  221.     putc('.', stderr); numper++;
  222.     matchlen = 0;
  223.     pos = DICSIZ;  insert_node();
  224.     if (matchlen > remainder) matchlen = remainder;
  225.     while (remainder > 0 && ! unpackable) {
  226.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  227.         get_next_match();
  228.         if (matchlen > remainder) matchlen = remainder;
  229.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
  230.             output(text[pos - 1], 0);
  231.         else {
  232.             output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  233.                    (pos - lastmatchpos - 2) & (DICSIZ - 1));
  234.             while (--lastmatchlen > 0) get_next_match();
  235.             if (matchlen > remainder) matchlen = remainder;
  236.         }
  237.     }
  238.     huf_encode_end();
  239.  
  240.     for (; numper < 15; numper++)
  241.         putc (' ', stderr);
  242. }
  243.